bloom filters

ähnliche laufzeit zu hashtabellen, wobei aber allein die existenz eines elements wichtig ist.typische anwendung hashset. platzeffizienz weil nicht das gesamte element gespeichert werden muss.

nur variationen implementieren löschen von elementen

false positive rate is nicht 0! (false negative rate schon)

hash fkt mapped input x -> bit pattern

k hashfunktionen

insert(W):
for i \leftarrow 1, 2, ..., k
    W[h_i(x)] \leftarrow 1

find:
B \leftarrow 0
insert(B, W)
return B & A == B
